In recent years, consumers have been provided with a variety of devices and systems to enable them to locate places or destinations on a digital map. The terms “places” or “destinations” are general terms used throughout the description of embodiments of this invention. The term “places” or “destinations” includes street addresses, buildings located at street addresses such as businesses and landmarks, and facilities located at a number of street addresses such as shopping malls and business parks. The variety of devices and systems used by consumers or “users” are in the form of in-vehicle navigation systems that enable drivers to navigate over streets and roads; hand-held devices such as personal digital assistants (“PDAs”), personal navigation devices (PNDs), and cell phones or other types of mobile devices that can perform navigation or utilize digital map data; desktop applications, and Internet applications in which users can generate maps showing desired places and use other mapping services, etc., collectively referenced herein as “end user mapping devices”. These end user mapping devices may be personal or commercial. The common aspect in all of these and other types of end user mapping devices is a map database of geographic features, vectors and attributes, and software to access, and/or manipulate, and/or navigate the map database in response to user inputs.
Essentially, in all of these end user mapping devices, a user can enter a desired place or destination and the returned result will be the location of that place or destination. Typically, users will enter the name of a business, such as a restaurant for example, or a destination landmark, such as the Golden Gate Bridge for example, or a street address, etc. The device/system then determines and returns the location of the requested place. The location may be shown on a map display, or may be used to calculate and display driving directions to the location in a known manner, or used in other ways.
As technology progresses, it becomes more and more important for a system to allow someone with the spatial content information or mapping information to communicate locations of dynamic content (known as a location reference, wherein a location reference can include one or more paths, and wherein non-limiting examples of a location reference include a traffic message such as a traffic jam, road closures, etc., a TMC location, a detour, a suggested tourist route, etc.), within the mapping information to travelers (via broadcasting packets of information to end user mapping devices including but not limited to in-vehicle and portable navigation devices (PNDs)) to enable routing between a location of a user and a desired destination of a user to occur in an improved, if not optimal, manner. For example, if a user of some type of navigation device or device with navigation capabilities, for example, can obtain a location of a location reference within mapping information indicating that there is a traffic jam along a stretch of highway that the user would be traveling on based upon his current route of travel, it would be desirable for the user of the navigation device to receive this information so that an improved route of travel could be calculated to avoid the traffic jam, for example.
Some methods broadcasting locations of such dynamic content or location references such as traffic jams, road closures, etc. is generally known (via broadcasting information packets to multiple remotely located end user mapping devices), as is re-routing of travel routes from obtained traffic information. The location on an encoding mapping device must be described in such a way that others receiving the information on a decoding device can understand the location of the traffic jam, road closure, etc. within stored spatial content or mapping information. However, the “location” may be mis-translated depending on a type or even version of map information that a decoding mapping device might be using (noting that the term “location reference” within the spatial content information may be more than just a point, namely it may be one or more paths or areas or anything that is a spatial description). Further, if too much information is conveyed, the speed of the location calculation at the end user mapping device may undesirably slow down.
Regarding the determination and conveying of a location reference, conveying of the information has been contemplated utilizing, for example, international codes for locations on stored maps for mapping applications. It is a current practice that a government agency or an industry consortium has authority to code the identity of each important spatial location such as a Traffic Message Channel code (TMC). However, such an authority has to maintain the codes, and the vendors of each of the databases or mapping application vendors have to incorporate these codes for subsequent application in all devices utilizing mapping applications. Such processes naturally limit the extent and currency of agreed upon location codes, which cover only a tiny fraction of map locations. Further, as the traffic reporting industry and mapping applications mature, the industry demands flexibility to reference a random location just in time, without pre-assigned codes, for dereferencing by mapping applications on map data from different map data suppliers or different data versions of the same supplier.
Thereafter, the mapping industry attempted to standardize what would be enough information, regarding location references (noting that a location reference may include one or more paths, and/or a traffic message such as a traffic jam or road closure location, a TMC location, a detour, a suggested tourist route, etc., which are all non-limiting examples of a location reference), to adequately convey a location within map information for example. Dynamic location referencing methods are designed so that irrespective of whose map or what map version is being used, enough information would be included to accurately reconstruct the referenced location within stored map information used in the decoding mapping device, such as a navigation device for example.
Typically, dynamic location reference methods go beyond just latitude and longitude of a traffic jam or road closure location, but also supply street and cross street names and other location properties. Modern map data is typically of good quality, being based on large scale area or satellite images and highly accurate field data collection, especially for high-usage locations. Yet there are still enough differences between data models, geometry and attributes and map data from different vendors and different versions of maps to make reliable road location referencing a non-trivial problem. Originating and decoding map data could be different in significant details between map data versions of the same vendor, and especially between two different vendors. The quality of dynamic location referencing methods is measured by location match rate between encoding and decoding devices. To reach an acceptable rate, some methods increase the amount of information provided regarding the location, which causes increased location encoding footprint, and requires inordinate encoding and decoding time. Thus, as the information content or location footprint become too large, decoding becomes a problem, especially in smaller end-user mapping devices which may not have significant processing power (such as portable navigation devices, for example).
Recently a method called Agora-C was developed as a location referencing standard aimed to meet a 95% decoding success rate on maps of different origins or of different versions, considered acceptable by the industry. However, the method is enormously complex, encoding is computationally intensive, and a location encoding footprint is relatively large, which may cause poor performance of the decoding process on small end user mapping devices.
Location referencing methods often utilize functional road class (FRC) as part of the encoding process, wherein roads are classified such as highways, small streets, etc. based on map data attributes. An FRC depicts the functional importance of a road, and is among the most common characteristic of linear feature encodings accepted by a variety of location referencing methods. Many location reference methods (including Agora-C) require computation of shortest paths in the process of encoding and decoding a location reference. In such methods, the shortest path computation which takes place in both an encoder of information and a decoder of information, is driven by a cost of travel along the link, wherein the more important the road, the cheaper the cost of travel per unit of distance.
Functional road class (FRC) is often used in route calculation of modern dynamic location reference methods (wherein Agora-C defines 10 FRCs, from low residential to the highest speed motorway, which are derived from map data). However, FRC attributes in map data are often results of a judgment call of a digital cartographer or field data collector, wherein mapmakers have no firm standard or agreements on FRCs. FRC values could be assigned based on a country's administrative road network scheme, speed limit, road vanity, reasons for providing a more beautified map display, or mixture of some or all of the reasons previously mentioned. Internal guidelines are subject to interpretation. Apart from topmost motorways or clearly residential streets, FRCs are therefore too vague to be considered reliably matched between versions of the database let alone, from one vendor's map database to another vendor's map database.
Accordingly, FRCs are often a likely culprit in location dereferencing errors, noting that differences in cost induced by ambiguous FRC mapping between different maps may cause significant difference in path computation by a decoding device, such as an end user mapping device 200 for example. Furthermore, introduction of massive amounts of probe data utilized for map data updating will subject mid-tier FRCs to a high rate of change, causing location referencing match rates to degrade even on data from different releases of the map databases from the same vendor.
An encoded location reference usually includes one or more paths, each including starting and ending points, and typically along with routing points or their equivalents, spatial markers, to help disambiguate a location on an encoding device, wherein routing points are placed along location reference paths such that connecting segments between each consecutive pairs of routing points coincide with the shortest path between them. A remote decoding device such as an end user mapping device, for example, identifies candidates for routing points and computes shortest paths between them to reconstruct an encoded location. While fast decoding speed is critical, a path reconstruction process on a decoding device often performs unnecessary work, exploring all potential routing nodes in a large area.